import java.util.Stack;
import java.util.ArrayList;
import java.util.List;
public class RegularUtil {

    /**
     *判断是否是一个合法的输入字符
     * @return
     */
    public boolean isDot(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z' || c >= '0' && c <= '9');
    }
    public boolean isCharacter(String c) {
        boolean res = true;
        for(int i = 0; i < c.length(); i++) {
            if (!(c.charAt(i) == '(' || c.charAt(i)==')' || c.charAt(i)=='#' ||c.charAt(i) == '|' || c.charAt(i) == '*' || isDot(c.charAt(i)) )) {
                res = false;
            }
        }
        return res;
    }
    /**
     *  判断左右括号是否匹配
     * 左括号入栈，右括号出栈，直到栈为空
     * 或匹配到右括号时栈是空的则返回false,报错右括号无法匹配
     * 或最后栈不空则返回false，报错左括号无法匹配
     * @return
     */
    public boolean isMatchParenthesis(String c) {
        Stack<Character> s = new Stack<Character>();
        int i=0;
        for (;i<c.length();i++) {
            //左括号入栈
            if(c.charAt(i) == '('){
                s.push(c.charAt(i));
            }
            //碰到右括号时左括号出栈
            if(c.charAt(i)==')'){
                //栈空则返回false，报错右括号无法匹配
                if(s.empty()){
                    System.out.println("右括号无法匹配");
                    return false;
                }else {
                    //左括号出栈
                    s.pop();
                }
            }
        }
        //如果栈不空则返回false，报错左括号无法匹配
        if(!s.empty()){
            System.out.println("左括号无法匹配");
            return false;
        }
        return true;
    }

    /**
     * 为中缀表达式间添加加号
     * @param Regular
     * @return
     */
    public String joinAddSymbol(String Regular) {
        int len = Regular.length();
        //初始值设置为一个足够大的数
        Character[] newRegex = new Character[10000];
        //下标
        int index=0;
        //设置pre和now遍历字符串
        Character preNode = Regular.charAt(0);
        Character nowNode = Regular.charAt(1);
        for(int i=0;i+1<len;i++){
            //赋值
            preNode = Regular.charAt(i);
            nowNode = Regular.charAt(i+1);
            newRegex[index++] = preNode;
            //在第一个字符和第二个字符之间添加+号
            if(isDot(preNode) && isDot(nowNode)){
                newRegex[index++] = '+';
            }else if( isDot(preNode) && nowNode=='('){
                //在字符和左括号之间插入+号
                newRegex[index++] = '+';
            }else if(preNode==')' && isDot(nowNode)){
                //在右括号和字符之间插入+号
                newRegex[index++] = '+';
            }else if(preNode=='*' && isDot(nowNode)){
                //在*号和字符之间插入+号
                newRegex[index++] = '+';//插入+号
            }
        }
        //将最后一个字符添加
        newRegex[index++] = nowNode;
        //转化为StringBuilder
        StringBuilder str = new StringBuilder();
        for(int i=0;i+1<10000;i++){
            //非空则添加
            if (newRegex[i] != null)
                str.append(newRegex[i]);
        }
        return str.toString();
    }

    /**
     * 中缀转后缀
     * @param regex
     * @return
     */
    public String infix_Suffix(String regex) {
        StringBuilder str = new StringBuilder();
        Stack<Character> s = new Stack<Character>();
        int n = regex.length();
        for(int i=0;i<n;i++){

//            System.out.println(str);
            char c = regex.charAt(i);
            //字符和*和#都直接拼接在str中
            if(isDot(c)){
                str.append(c);
            }else if(c=='*'){
                str.append(c);
            }else if(c=='('){
                s.push(c);
            }else if(c==')'){
                //碰到右括号的时候直接将栈中的元素依次出栈，直到遇到左括号
                while(s.peek()!='('){
                    str.append(s.pop());
                }
                //左括号出栈
                s.pop();
            }else if(c=='|'){
                //碰到|将栈中左括号之后的全部出栈并加入str
                while(!s.empty() && s.peek()!='('){
                    str.append(s.pop());
                }
                //|入栈
                s.push(c);
            }else if(c=='+'){
                //将栈中左括号之后的全部出栈并加入str
                while(!s.empty() && s.peek()!='('){
                    str.append(s.pop());
                }
                s.push(c);
            }else if (c=='#'){
                str.append(c);
            }
        }

        while(!s.empty()){
            str.append(s.pop());
        }
        return str.toString();
    }

    /**
     * 将G2中的边集复制到G1
     * @param G1
     * @param G2
     */
    public void duplicateArc(NFAGraph G1, NFAGraph G2)
    {
        int i;
        //遍历c2，将c2中边集复制到c1
        for (i = 0; i < G2.arcCount; i++)
        {
            G1.arcCollection[G1.arcCount + i] = G2.arcCollection[i];
        }
        G1.arcCount += G2.arcCount;
    }

    /**
     * 构造单个结点的NFA
     * @param ch
     * @return
     */
    public NFAGraph initState(char ch) {
        State startState = new State();
        State endState = new State();
        Arc[] arcCollection = new Arc[1000];
        List<State> endList = new ArrayList<State>();
        Arc newArc = new Arc(startState, endState);
        NFAGraph newGraph = new NFAGraph(arcCollection, startState,  endList);
        newArc.start.name = Global.STATE_NAME++;
        newArc.end.name = Global.STATE_NAME++;
        newArc.access = ch;

        //边数初始化为0
        newGraph.arcCount = 0;
        //将新的边加入边集
        newGraph.arcCollection[newGraph.arcCount++] = newArc;
        //将边的开始状态设为NFA的开始状态
        newGraph.startState = newArc.start;
        //将边的终止状态加入为NFA的终止状态集
        newGraph.endStateList.add(newArc.end);
        return newGraph;

    }

    /**
     * +号的运算规则
     * @param in_Left
     * @param in_Right
     * @return
     */
    public NFAGraph join_Graph(NFAGraph in_Left, NFAGraph in_Right) {
        RegularUtil util = new RegularUtil();
        State startState = new State();
        Arc[] arcCollection = new Arc[1000];
        List<State> endList = new ArrayList<State>();
        NFAGraph Right = new NFAGraph(arcCollection, startState,  endList);
        Right = in_Right;

        int i = 0;
        for (i = 0; i < Right.arcCount; i++){
            //如果右边的边的开始状态是右边的startState，则将该边的开始状态设为左边的终止结点
            if (Right.arcCollection[i].start.name == Right.startState.name)
            {
                Right.arcCollection[i].start = in_Left.endStateList.get(0);
            }
            //如果右边的边的终止状态是右边的startState，则将该边的终止状态设为左边的终止结点
            else if (Right.arcCollection[i].end.name == Right.startState.name)
            {
                Right.arcCollection[i].end = in_Left.endStateList.get(0);
            }
        }
        //右边的开始状态改为左边的终止状态
        Right.startState = in_Left.endStateList.get(0);
        for (i = 0; i < Right.arcCount; i++){
            // 将所有边的开始状态或者终止状态为右边终止结点的边的终止结点的值缩小一位
            if (Right.arcCollection[i].end.name == Right.endStateList.get(0).name)
            {
                Right.arcCollection[i].end.name--;
                Right.endStateList.get(0).name++;
            }
            if (Right.arcCollection[i].start.name == Right.endStateList.get(0).name)
            {
                Right.arcCollection[i].start.name--;
                Right.endStateList.get(0).name++;
            }
        }

        //右边终止结点缩小一位
        Right.endStateList.get(0).name--;
        Global.STATE_NAME--;

       //result将右边的边复制过来左边，将左边返回
        duplicateArc(in_Left, Right);

        in_Left.endStateList = Right.endStateList;

        return in_Left;
    }

    /**
     * |运算的运算规则
     * @param in_Left
     * @param in_Right
     * @return
     */
    public NFAGraph union_Graph(NFAGraph in_Left, NFAGraph in_Right) {
        State startState = new State();
        State endState = new State();
        Arc[] arcCollection = new Arc[1000];
        List<State> endList = new ArrayList<State>();
        NFAGraph newGraph = new NFAGraph(arcCollection, startState,  endList);
        //初始化边集数为0
        newGraph.arcCount = 0;
        //NFA的开始结点
        newGraph.startState.name = Global.STATE_NAME++;
        State newEndState = new State();
        newEndState.name = Global.STATE_NAME++;
        boolean test1 = true;

        //将NFA的终止结点加入到NFA的终止结点集中
        newGraph.endStateList.add(newEndState);
        //初始化四条边
        Arc edge1 = new Arc(startState, endState);
        Arc edge2 = new Arc(startState, endState);
        Arc edge3 = new Arc(startState, endState);
        Arc edge4 = new Arc(startState, endState);

        //设置四条边的值
        // 新开始节点指向Left开始节点
        edge1.start = newGraph.startState;
        //开始结点的结尾指向其中一个结点开头
        edge1.end = in_Left.startState;
        edge1.access = '#';

        // 新开始节点指向Right开始节点
        edge2.start = newGraph.startState;
        //开始结点的结尾指向其中一个结点开头
        edge2.end = in_Right.startState;
        edge2.access = '#';


        edge3.start = in_Left.endStateList.get(0);
        // Left终止节点指向新终止节点
        edge3.end = newGraph.endStateList.get(0);
        edge3.access = '#';

        edge4.start = in_Right.endStateList.get(0);
        // Right终止节点指向新终止节点
        edge4.end = newGraph.endStateList.get(0);
        edge4.access = '#';

        // 将Left和Right的边集复制到新的NFA中
        duplicateArc(newGraph, in_Left);
        duplicateArc(newGraph, in_Right);

        // 将值设置完之后将新增的边加入
        newGraph.arcCollection[newGraph.arcCount++] = edge1;
        newGraph.arcCollection[newGraph.arcCount++] = edge2;
        newGraph.arcCollection[newGraph.arcCount++] = edge3;
        newGraph.arcCollection[newGraph.arcCount++] = edge4;

        return newGraph;
    }

    /**
     * 闭包的运算规则
     * @param temp
     * @return
     */
    public NFAGraph star_Graph(NFAGraph temp) {
        State endState = new State();
        State startState = new State();
        Arc[] arcCollection = new Arc[1000];
        List<State> endList = new ArrayList<State>();
        NFAGraph tempGraph = new NFAGraph(arcCollection, startState,  endList);
        //初始化边集为0
        tempGraph.arcCount = 0;
        tempGraph.startState.name = Global.STATE_NAME++;
        State newEndState = new State();
        newEndState.name = Global.STATE_NAME++;

        boolean test1 = true;
        tempGraph.endStateList.add(newEndState);

        //初始化四条边
        Arc edge1 = new Arc(startState, endState);
        Arc edge2 = new Arc(startState, endState);
        Arc edge3 = new Arc(startState, endState);
        Arc edge4 = new Arc(startState, endState);

        //开始设置四个结点的值
        // 新的开始节点指向原来的开始结点
        edge1.start = tempGraph.startState;
        edge1.end = temp.startState;
        edge1.access = '#';

        // 原来的终止结点指向新的终止节点
        edge2.start = temp.endStateList.get(0);
        edge2.end = tempGraph.endStateList.get(0);
        edge2.access = '#';

        // 原来的终止节点指向原来的开始节点的边
        edge3.start = temp.endStateList.get(0);
        edge3.end = temp.startState;
        edge3.access = '#';

        // 新的开始结点指向新的终止节点
        edge4.start = tempGraph.startState;
        edge4.end = tempGraph.endStateList.get(0);
        edge4.access = '#';

        // 将原来NFA中的边复制到新的NFA中
        duplicateArc(tempGraph, temp);
        // 将新增的四条边加入新的NFA中
        tempGraph.arcCollection[tempGraph.arcCount++] = edge1;
        tempGraph.arcCollection[tempGraph.arcCount++] = edge2;
        tempGraph.arcCollection[tempGraph.arcCount++] = edge3;
        tempGraph.arcCollection[tempGraph.arcCount++] = edge4;

        return tempGraph;
    }
}
